The invention relates to computer system recovery, and in particular to synchronization of database indexes to the data spaces which they cover.
Databases may be comprised of data spaces that contain data space entries, or records, and database indexes that provide ordered lists of data space entries, based on key values contained in the data space entries. When changes are made to the entries in a data space(s), database indexes over the data space may need to be updated, in order to keep the indexes synchronized with respect to the data space they cover. In the IBM System/38, the changes to the database index(es) are made first, followed by the changes to the data space. This order of changes is chosen to allow any conditions that would prevent the updating of the database indexes to surface before a data space is changed. The attempt to insert a duplicate key into a unique index is one such condition.
When the system terminates abnormally, the data spaces and the database indexes relating thereto may not be synchronized. Some transactions may have caused database index(es) to be updated, but the associated data space entries may not have been updated at the time the system terminated. To further complicate matters, in a virtual storage environment with paging, the paging routine may not have written the changed pages for either the data space or the associated database index(es) to nonvolatile storage, or it may have only written some of the changed pages for either the data space or the database index(es) to nonvolatile storage at the time of a failure. If some, but not all, of the changed pages for a database index were written to nonvolatile storage before an abnormal termination, the logical structure of the index that is available from nonvolatile storage after termination may be sufficiently inconsistent so as to preclude use of the index, even as a starting point for forward recovery (using a journal of data space entry changes).
Journaling of transactions which cause a change in a database is a well known technique, and is described in detail in the following references: U.S. Pat. No. 4,507,751 to Gawlick et al., Haerder, "Principles of Transaction-Oriented Recovery", Computing Surveys, Vol. 15, No. 4 Dec. 1983, Verhofstad, "Recovery Techniques for Database Systems", Computing Surveys, Vol. 10, No. 2, June 1978, and Gray, "The Recovery Manager of the System R Database Manager", Computing Surveys, Vol. 13, No. 2, June 1981. These references do not address efficient recovery of database indexes relating to data spaces.
Journaling transactions to a database works well for recovery of the data space, because it is only necessary to journal the image of each data space entry before and after each change. Each data space entry is localized at a fixed position within the data space, so few pages are changed when a data space entry is updated.
Journaling the changes to the database indexes relating to a data space is more complex because, depending on the type of data structure used for the index, a change to a single entry in an index may require changes to many logical pages in the index. Many popular index structures, such as binary radix trees and B-trees, exhibit the characteristic that a change to a single entry can require changes distributed through many logical pages of the index. An approach of journaling all changes to a database index may require so many pages to be journaled for each change of a data space entry that the technique cannot be used because of the very large storage requirements for the journal or because the performance cost of the required journal activity may be prohibitive.
The most straight-forward approach to recovering database indexes following a failure, where the state of indexes is uncertain, is to read every entry in every data space covered by each database index, and rebuild the entire index from the data space entries. This process can be extremely time-consuming, because of the number of auxiliary storage I/O operations and index operations required. In some cases, the time required to recover the database indexes over one or more large data spaces is measured in terms of days.